package com.le.tester.leetcode;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

/**
 * createTime：2023/2/16 10:05
 * description：三角形最小路径和
 */
public class MinimumTotal {
    public int minimumTotal(List<List<Integer>> triangle) {

        int size = triangle.size();
        int[][] f = new int[size][size];
        //第一个是固定值
        f[0][0] = triangle.get(0).get(0);

        for (int i = 1; i < size; i++) {
            f[i][0] = triangle.get(i).get(0) + f[i - 1][0];
            for (int j = 1; j < i; j++) {
                f[i][j] = f[i][j] = Math.min(f[i - 1][j - 1], f[i - 1][j]) + triangle.get(i).get(j);
            }
            //三角形的每一行的最后一个值
            f[i][i] = f[i - 1][i - 1] + triangle.get(i).get(i);
        }

        int minTotal = f[size - 1][0];
        for (int i = 1; i < size; i++) {
            minTotal = Math.min(minTotal, f[size - 1][i]);
        }

        return minTotal;
    }

    public static void main(String[] args) {
        List<Integer> inList1 = new ArrayList<>();
        List<Integer> inList2 = new ArrayList<>();
        List<Integer> inList3 = new ArrayList<>();
        List<Integer> inList4 = new ArrayList<>();
        List<List<Integer>> outList = new ArrayList<>();

        inList1.add(2);

        inList2.add(3);
        inList2.add(4);

        inList3.add(6);
        inList3.add(5);
        inList3.add(9);

        inList4.add(4);
        inList4.add(4);
        inList4.add(8);
        inList4.add(0);


        outList.addAll(Collections.singleton(inList1));
        outList.addAll(Collections.singleton(inList2));
        outList.addAll(Collections.singleton(inList3));
        outList.addAll(Collections.singleton(inList4));
        System.out.println(new MinimumTotal().minimumTotal(outList));


    }
}
